The Discrete Fourier Transform (DFT) transforms a discrete time-domain sequence of finite length into a discrete set of frequency values. The DFT of an N-point sequence x(n) is
            X      ⁡              (        k        )              =                            ∑                      n            =            0                                N            -            1                          ⁢                                  ⁢                              x            ⁡                          (              n              )                                ⁢                      W            N            kn                    ⁢                                          ⁢          for          ⁢                                          ⁢          k                    =      0        ,  1  ,            …      ⁢                          ⁢      N        -    1.  WN, often referred to as a twiddle factor, is shorthand notation for e−j2π/N. The inverse DFT (IDFT) relation is identical to the DFT relation scaled by a constant and with the sign of the exponent reversed:
            x      ⁡              (        n        )              =                            1          N                ⁢                              ∑                          k              =              0                                      N              -              1                                ⁢                                          ⁢                                    X              ⁡                              (                k                )                                      ⁢                          W              N                              -                kn                                      ⁢                                                  ⁢            for            ⁢                                                  ⁢            n                              =      0        ,  1  ,            …      ⁢                          ⁢      N        -    1.  Therefore, techniques developed for the DFT apply with minimal adaptation to the IDFT.
The DFT is capable of handling complex x(n), in which case the DFT will transform N (or fewer) complex time-domain inputs into N complex frequency-domain outputs. Because WN is complex, the X(k) generated by the DFT are often complex, even when the input sequence x(n) is real. If the DFT of a sequence of length 2N is desired, a 2N-point DFT can be used. If the 2N-point sequence is real, however, it seems intuitively possible to arrange pairs of the 2N real inputs to make N complex inputs. This N-point complex input can then be processed with an N-point DFT. This technique will be useful if the 2N-point DFT can be extracted from this N-point DFT.
If a sequence containing 2N real values is denoted g(n), two N-point real sequences can be formed from g(n). These N-point sequences may contain the even and odd points of g(n), respectively: e.g., x1(n)=g(2n) and x2(n)=g(2n+1). These two sequences can be combined into a single complex sequence of length N by assigning x1(n) as the real part and x2(n) as the imaginary part: i.e., x(n)=x1(n)+jx2(n). The 2N-point real sequences can be expressed in terms of the combined sequence as follows:
            x      1        ⁡          (      n      )        =                              1          2                ⁡                  [                                    x              ⁡                              (                n                )                                      +                          x              *                              (                n                )                                              ]                    ⁢                          ⁢      and      ⁢                          ⁢                        x          2                ⁡                  (          n          )                      =                  1                  2          ⁢                                          ⁢          j                    ⁡              [                              x            ⁡                          (              n              )                                -                      x            *                          (              n              )                                      ]            The DFT is a linear relation, so:
                    X        1            ⁡              (        k        )              =                            1          2                ⁡                  [                                    D              ⁢                                                          ⁢              F              ⁢                                                          ⁢                              T                ⁡                                  (                                      x                    ⁡                                          (                      n                      )                                                        )                                                      +                          D              ⁢                                                          ⁢              F              ⁢                                                          ⁢                              T                ⁡                                  (                                      x                    *                                          (                      n                      )                                                        )                                                              ]                    ⁢                          ⁢      and                          ⁢                            X          2                ⁡                  (          k          )                    =                                    1                          2              ⁢                                                          ⁢              j                                ⁡                      [                                          D                ⁢                                                                  ⁢                F                ⁢                                                                  ⁢                                  T                  ⁡                                      (                                          x                      ⁡                                              (                        n                        )                                                              )                                                              -                              D                ⁢                                                                  ⁢                F                ⁢                                                                  ⁢                                  T                  ⁡                                      (                                          x                      *                                              (                        n                        )                                                              )                                                                        ]                          .            Symmetry of the DFT means that:
            X      1        ⁡          (      k      )        =                              1          2                ⁡                  [                                    X              ⁡                              (                k                )                                      +                          X              *                              (                                  N                  -                  k                                )                                              ]                    ⁢                          ⁢      and      ⁢                          ⁢                        X          2                ⁡                  (          k          )                      =                            1                      2            ⁢                                                  ⁢            j                          ⁡                  [                                    X              ⁡                              (                k                )                                      -                          X              *                              (                                  N                  -                  k                                )                                              ]                    .      
The desired output is the DFT G(k) of the original 2N input sequence g(n). The definition of the DFT can be used to reconstruct G(k), where
                    G        ⁡                  (          k          )                    =                                    ∑                          n              =              0                                                      2                ⁢                                                                  ⁢                N                            -              1                                ⁢                                          ⁢                                    g              ⁡                              (                n                )                                      ⁢                          W                              2                ⁢                                                                  ⁢                N                            kn                                      =                                                            ∑                                  n                  =                  0                                                  N                  -                  1                                            ⁢                                                          ⁢                                                g                  ⁡                                      (                                          2                      ⁢                                                                                          ⁢                      n                                        )                                                  ⁢                                  W                                      2                    ⁢                                                                                  ⁢                    N                                                        2                    ⁢                                                                                  ⁢                    kn                                                                        +                                          ∑                                  n                  =                  0                                                  N                  -                  1                                            ⁢                                                          ⁢                                                g                  ⁡                                      (                                                                  2                        ⁢                                                                                                  ⁢                        n                                            +                      1                                        )                                                  ⁢                                  W                                      2                    ⁢                                                                                  ⁢                    N                                                        k                    ⁡                                          (                                                                        2                          ⁢                                                                                                          ⁢                          n                                                +                        1                                            )                                                                                                    =                                                                      ∑                                      n                    =                    0                                                        N                    -                    1                                                  ⁢                                                                  ⁢                                                                            x                      1                                        ⁡                                          (                      n                      )                                                        ⁢                                      W                    n                    kn                                                              +                                                W                                      2                    ⁢                                                                                  ⁢                    N                                    k                                ⁢                                                      ∑                                          n                      =                      0                                                              N                      -                      1                                                        ⁢                                                                          ⁢                                                                                    x                        2                                            ⁡                                              (                        n                        )                                                              ⁢                                          W                      N                      nk                                                                                            =                                                                                X                    1                                    ⁡                                      (                    k                    )                                                  +                                                      W                                          2                      ⁢                                                                                          ⁢                      N                                        k                                    ⁢                                                            X                      2                                        ⁡                                          (                      k                      )                                                                                  =                                                1                  2                                ⁢                                  (                                                            {                                                                        X                          ⁡                                                      (                            k                            )                                                                          +                                                                              X                            *                                                    ⁡                                                      (                                                          N                              -                              k                                                        )                                                                                              }                                        -                                          j                      ⁢                                                                                          ⁢                                              W                                                  2                          ⁢                                                                                                          ⁢                          N                                                k                                            ⁢                                              {                                                                              X                            ⁡                                                          (                              k                              )                                                                                -                                                                                    X                              *                                                        ⁡                                                          (                                                              N                                -                                k                                                            )                                                                                                      }                                                                              )                                                                          ⁢                                    ⁢                            for          ⁢                                          ⁢          k                =        0            ,      1      ,      …      ⁢                          ,              N        -        1            The DFT of a real sequence is Hermitian symmetric:
            G      ⁡              (                              2            ⁢            N                    -          k                )              *    =                    [                              ∑                          n              =              0                                                      2                ⁢                N                            -              1                                ⁢                                          ⁢                                    g              ⁡                              (                n                )                                      ⁢                          W                              2                ⁢                                                                  ⁢                N                                                              (                                                            2                      ⁢                                                                                          ⁢                      N                                        -                    k                                    )                                ⁢                n                                                    ]            *        =                                        W                          2              ⁢                                                          ⁢              N                                      2              ⁢                                                          ⁢              Nn                                ⁡                      [                                          ∑                                  n                  =                  0                                                                      2                    ⁢                                                                                  ⁢                    N                                    -                  1                                            ⁢                                                          ⁢                                                g                  ⁡                                      (                    n                    )                                                  ⁢                                  W                                      2                    ⁢                                                                                  ⁢                    N                                                        -                    kn                                                                        ]                          *            =                                    ∑                          n              =              0                                                      2                ⁢                                                                  ⁢                N                            -              1                                ⁢                                          ⁢                                                                      [                                      g                    ⁡                                          (                      n                      )                                                        ]                                *                            ⁡                              [                                  W                                      2                    ⁢                                                                                  ⁢                    N                                                        -                    kn                                                  ]                                      *                          =                                            ∑                              n                =                0                                                              2                  ⁢                                                                          ⁢                  N                                -                1                                      ⁢                                                  ⁢                                          g                ⁡                                  (                  n                  )                                            ⁢                              W                                  2                  ⁢                                                                          ⁢                  N                                kn                                              =                      G            ⁡                          (              k              )                                          
Therefore, once the first N points are calculated, the next N are simply the complex conjugates of the first N in reverse order. Interleaving real g(n) into a complex sequence x(n) may be accomplished by the way in which g(n) is initially stored in memory. For example, g(n) may be stored in memory sequentially, and complex numbers may be read as alternating real and imaginary parts. Calculation is therefore divided into two steps: the DFT and post-processing. A computational reduction of approximately two times is achieved in the DFT step by using an N-point DFT instead of a 2N-point DFT, a savings that becomes more significant as N increases.
This technique is discussed in John G. Proakis & Dimitris G. Manolakis, Digital Signal Processing: Principles, Algorithms, and Applications § 6.2.2 (3d ed. 1996), which is hereby incorporated by reference in its entirety. Referring now to FIG. 1, the flow of data is summarized for an exemplary sequence length. An 8192-point real sequence 50 is split into two 4096-point real sequences 52 consisting of the even and odd values of the original sequence 50. The even and odd real sequences form the real and imaginary parts, respectively, of a 4096-point complex sequence 54. A 4096-point DFT transforms the complex sequence 54 into a 4096-point frequency domain sequence 56. Post-processing creates a new 4096-point sequence 58. Hermitian symmetry dictates what the next 4096 points are, to allow generation of a 8192-point complex sequence 60.
The technique is equally applicable when calculating the IDFT of a 2N-point frequency domain sequence G(k) that is Hermitian symmetric (corresponding to a real time-domain sequence). This is the case in VDSL (Very high bit-rate Digital Subscriber Line) applications. In this situation, the calculation steps are pre-processing and IDFT calculation. Pre-processing involves calculating
            X      1        ⁡          (      k      )        =            1              2        ⁢                                        ⁡          [                        G          ⁡                      (            k            )                          +                              G            ⁡                          (                              N                -                k                            )                                *                    ]      and
            X      2        ⁡          (      k      )        =                    1        2            ⁡              [                              G            ⁡                          (              k              )                                -                                    G              ⁡                              (                                  N                  -                  k                                )                                      *                          ]              ⁢          ⅇ              j2π        ⁢                                  ⁢                  k          /          N                    and from the first N points of G(k) (the next N points add no information, as they are simply conjugates of the first N according to Hermitian symmetry). The sequence upon which the IDFT is performed is X(k)=X1(k)+jX2(k), and the resulting sequence x(n) will contain the even samples x1(n) as the real parts, and the odd samples x2(n) as the imaginary parts.
Referring now to FIG. 2, a data flow summary of this inverse process is depicted. A 4096-point complex sequence 70 (although Hermitian symmetry dictates the other 4096 points of a 8192-point sequence) is pre-processed to another 4096-point complex sequence 72. An IDFT transforms the sequence 72 into a 4096-point complex sequence 74. The real and imaginary parts 76 of the complex sequence 74 are the even and odd values, respectively, of an 8192-point real sequence 78.
Referring now to FIG. 3, a data flow summary of a similar technique is depicted. In this case, the DFT of two real sequences is desired. The two 4096-point real sequences 90 form the real and imaginary parts of a 4096-point complex sequence 92. A DFT transforms the sequence 92 into another 4096-point complex sequence 94. Post-processing extracts two 4096-point complex sequences 96 from the sequence 94. The sequences 96 are the DFTs of the respective sequences 90.
Referring now to FIG. 4, a data flow summary of the process inverse to that of FIG. 3 is shown. Two 4096-point complex sequences 100 are added (multiplying the second sequence 100 by j) to create a 4096-point complex sequence 102. An IDFT transforms the sequence 102 into a 4096-point complex sequence 104. The real and imaginary parts of the sequence 104 are the respective values of two 4096-point real sequences 106. The sequences 106 correspond to the IDFTs of the sequences 100.
The DFT can be evaluated directly according to its definition,
      X    ⁡          (      k      )        =            ∑              n        =        0                    N        -        1              ⁢                  ⁢                  x        ⁡                  (          n          )                    ⁢                        W          N          kn                .            Due to the DFT's importance, many techniques have been developed that speed this process. These techniques are generally labeled Fast Fourier Transforms (FFT), and have complementary Inverse FFTs (IFFT). The above technique for obtaining a 2N-point DFT sequence using only an N-point DFT is equally applicable when an FFT is used to calculate the DFT.
One popular FFT methodology is referred to as divide-and-conquer. For N=L*M, the divide-and-conquer FFT will calculate L M-point DFTs and combine the L DFTs into a single DFT. For example, if M is 2, L 2-point DFTs can be calculated. If N is a power of 2, this division can be repeated log2 N times. This FFT is known as Radix-2. If N is a power of 4, a Radix-4 FFT can be used. The Radix-4 FFT is more complex to implement, but for large N, its reduction in computation time is worth the trade-off. Because an input sequence can be zero-padded up to a length of a power of 2 or 4, Radix-2 and Radix-4 can be used for any input sequence.